The present invention relates to block interleaver and de-interleaver structures for changing the orders of values in a data stream.
Interleavers are memory structures widely used in wireless communications, where streams of data (e.g., voice data) must be transmitted through the air from a source device to a receiver. Groups of sequential bits in these streams of data are subject to noise errors (i.e., value changes during transmission) in the presence of a burst noise event or during fading of the transmission signal.
To protect against noise, conventional systems implement error correction schemes in which the source device adds redundant bits to the data stream, and the receiver implements an algorithm to detect and correct noise errors. Most error correction schemes work reasonably well as long as the erroneous bits are spread throughout the bit stream (after the addition of the error-correction bits). Unfortunately, these error correction schemes fail to correct continuous sequences of erroneous bits.
An interleaver/de-interleaver system is typically used to enable the correction of continuous sequences of erroneous bits in the transmitted data stream. In such a system, an interleaver is provided in the source device to scramble the order of the bits of the data stream prior to transmission. A de-interleaver is provided in the receiver to de-scramble the order of the bits after transmission, thereby reconstructing the data stream in the original order. A noise event occurring during transmission will therefore corrupt sequential bits in the scrambled data stream, which correspond with non-sequential bits in the original data stream. Thus, after the de-interleaver de-scrambles the order of the bits, the erroneous bits will be spread throughout the data stream. A conventional error correction scheme can then be applied to the data stream provided by the de-interleaver to correct the erroneous bits. A basic description of interleavers is provided in U.S. Pat. No. 3,652,998 by Forney.
A commonly used method of interleaving is block interleaving. In this method, the data to be transmitted is divided to blocks, typically of equal length. Each block is interleaved separately. At the receiver, blocks are de-interleaved and concatenated again to form a continuous bit stream.
In a simple interleaving scheme, a special random access memory (RAM) is used to perform the interleaving. Sequential data values are written into the RAM in row order, and then read out of the RAM in column order. In this manner, the sequential data values are scrambled. For example, sequential data values D1-D12 would be written into a 3xc3x974 RAM in row order as defined below in Table 1.
When the data values are sequentially read from columns 1, 2 and 3 of the RAM (i.e., in column order), the order of the data values D1-D12 will be: D1, D4, D7, D10, D2, D5, D8, D11, D3, D6, D9, and D12. This is the order in which the data values are transmitted.
Although Table 1 defines a block interleaver having a size of twelve bits, in practice, much longer interleaver blocks are used to protect against longer bursts of noise and fading periods. For example, interleaver blocks of more than 20,000 bits are used in most of the 3rd generation telephony standards (when high bit rates are transmitted).
More complex block interleaver schemes include permutation of order in which the columns are read. For example, data values might be sequentially read from columns 1, 3 and 2 of the RAM. In this case, the order of the transmitted data values will be D1, D4, D7, D10, D3, D6, D9, D12, D2, D5, D8 and D11.
Static RAM (SRAM) devices are typically used to implement block interleavers. Because an access of a large SRAM device consumes a relatively high power, it is desirable to minimize the number of SRAM accesses in the process of block interleaving.
In general, power consumption of an SRAM device may be reduced if the memory word width is large, so that several bits are accessed at the same time. But for a block interleaver, the SRAM device is written in rows and read in columns. If the SRAM block interleaver is arranged so that each row stores one or more memory words, then each write operation to the SRAM block interleaver can be performed one or more word at a time, in a power-efficient manner. However, read operations from the SRAM block interleaver must be performed in a per-column manner, with one memory-read cycle required for every bit read (a full word will be read, but only one of the bits will be used).
Returning to Table 1, and assuming a word length of 3 bits (a full row), the block interleaver will be written during four cycles. Thus, during a first cycle, data values D1-D3 are written to Row 1, during a second cycle, data values D4-D6 are written to Row 2, during a third cycle, data values D7-D9 are written to Row 3, and during a fourth cycle, data values D10-D12 are written to Row 4.
It will take twelve cycles to extract the twelve data values D1-D12 from the block interleaver. Table 2 defines these twelve cycles.
In general, if the word length is W and the block interleaver memory size is M bits, where M is a multiple of W, then an interleaving procedure will have a duration of M/W write cycles and M read cycles.
If an SRAM block interleaver is selected where columns are configured to store words, then M/W read cycles will be required, thereby making the read operations more efficient. However, such a configuration would require M write cycles, thereby making the write operations less efficient. As a result, power consumption will remain high.
It would therefore be desirable to have a block interleaver capable of overcoming the deficiencies of the described prior art, thereby exhibiting reduced power consumption.
The present invention provides a block interleaver that includes a relatively small register file and a larger interleaver RAM. In one embodiment, the size of the interleaver RAM is larger than the size of the register file by at least one order of magnitude. As a result, the register file consumes significantly less power than the interleaver RAM for similar operations.
The register file is used for intermediate storage of the data values (bits or symbols) in a sequential input data stream. Data values to be written into the interleaver RAM are first written to the register file in a column order. Then, the data values are transferred from the register file to the interleaver RAM in a row order. This transfer is performed using write operations to the interleaver RAM, wherein the width of the write operations is equal to the full width of the interleaver RAM. In one embodiment, the data values are written to the interleaver RAM in a staggered row order. In another embodiment, the data values are written to the interleaver RAM in a row order, which is selected to implement a permutation of a column order of the original data stream.
Data values are then read from the interleaver RAM in a row order, thereby creating an interleaved data stream. Each of these read operations has a width equal to the full width of the interleaver RAM. In a particular embodiment, the data values are read from the interleaver RAM in a sequential row order.
Because all read and write accesses to the interleaver RAM are performed using the full width of the interleaver RAM, no unnecessary power is used to transfer data values through the RAM. The register file consumes significantly less power than the RAM, thereby providing an overall power savings for the interleaving process. In addition, the interleaver RAM enables faster transfer rates as the read and write operations are performed in words and not in bits. In different embodiments, the register file can be a single-port device, a dual-port device, or multiple devices.
In another embodiment, the present invention provides a block de-interleaver that includes a relatively small register file and a larger de-interleaver RAM. Data values from an interleaved data stream are first written to the de-interleaver RAM in a first row order. The width of these write operations is equal to the full width of the de-interleaver RAM. Then, the data values are transferred from the de-interleaver RAM to the register file in a second row order. This transfer is performed using read operations from the de-interleaver RAM, wherein the width of these read operations is equal to the full width of the de-interleaver RAM. In one embodiment, the first row order is a sequential row order and the second row order is a staggered row order. In another embodiment, the second row order is selected to eliminate a column permutation present in the interleaved data stream.
Data values are then read from the register file in a column order, thereby providing a de-interleaved data stream. Because all read and write accesses to the interleaver RAM are performed using the full width of the interleaver RAM, no unnecessary power is used to transfer data values through the RAM. The register file consumes significantly less power than the RAM, thereby providing an overall power savings for the interleaving process. In different embodiments, the register file can be a single-port device, a dual-port device, or multiple devices.